package com.zyk.leetcode;

import java.util.Deque;
import java.util.LinkedList;

/**
 *
 * https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/
 *
 * @author zhangsan
 * @date 2021/3/24 11:22
 */
public class M59 {

    public int[] maxSlidingWindow(int[] nums, int k) {
        if( nums==null || k<1 || nums.length<k ) {
            return null;
        }
        int[] result = new int[nums.length-k+1];
        int index = 0;
        Deque<Integer> deque = new LinkedList<Integer>();

        for (int r = 0; r < nums.length; r++) {
            while ( !deque.isEmpty() && nums[deque.peekLast()] <= nums[r] ) {
                deque.pollLast();
            }
            deque.addLast(r);
            if( r- k == deque.peekFirst() ) {
                deque.pollFirst();
            }
            if( r>= k-1 ) {
                result[index++] = nums[deque.peekFirst()];
            }
        }
        return result;
    }

    public static void main(String[] args) {

    }

}
